Variable length codes (VLC) are widely used in data compression and particularly in image compression. The set of possible codewords are assigned codes of varying lengths. More frequently used codewords are assigned shorter codes than less frequently used codewords. Exploiting such frequency of use achieves additional data compression because short assigned codes are used more frequently than long assigned codes.
Variable length code decoding is typically implemented using lookup tables. Because the length of the codeword is not known before decoding, the lookup table will include redundant entries corresponding to whatever bits follow the codeword. For instance, if the codeword is 001100 but 7 bits are used for the lookup table index, then either 0011000 or 0011001 correspond to the same codeword. Often the amount of lookup table memory needed can be reduced by narrowing the search based on the number of leading zeroes in the code and using multiple tables. Many devices use hardware accelerators that exploit this leading zero property. Even software only techniques for decoding VLCs typically exploit this property in order to reduce the needed lookup table memory.
Reversible variable length code (RVLC) codewords can be decoded in either the forward or backward direction. This property is believed useful in error recovery, when a special start code or marker follows the RVLC part of the bitstream. A single bit error in the bitstream may result in improper decoding. If the erroneously decoded word has a different length than the correct codeword, then the decoder would be operating on incorrect variable length code thereafter. This error might not be immediately detected. Some later decoding error based on incorrect word boundaries may alert the decoder to existence of the prior error. In that case, some of the uncorrupted data that follows the bit errors may be recovered by decoding the RVLC codewords backwards from the start code that marks the end of the RVLC codewords.
This special structure of reversible variable length codewords means they cannot be decoded efficiently using the techniques generally used for decoding VLCs (variable length codewords). This property is useful for error recovery. Because RVLCs are encoded for error resilience or large free distance, the resulting codetree is sparse but does not include the leading zeros structure of typical VLCs. This makes efficient table lookup difficult. Thus the special structure of RVLC codewords makes the decoding techniques used for regular VLC codewords are less efficient.
For example, the Simple-profile MPEG-4 has the option of using reversible variable length codewords. However, in the RVLC used in the Simple-profile MPEG-4 video standard, all but a few codewords have exactly one leading zero. Using a hardware coprocessor exploiting the leading zero parsing typically used in VLCs, the lookup tables require almost 21 K words. This amount would generally exceed the device buffer limitations. Thus there is a need in the art to reduce the amount of lookup table memory needed to decode RVLCs while using the common leading zeros decode techniques.